A trie, or prefix tree, is an ordered tree data structure that can be used to store a dynamic set or associative array in which the keys may be, for example, character strings. In a trie, the position of a particular node defines the key with which it is associated. All descendants of a node have a common prefix of the string associated with that node, and the root is associated with an empty string. A respective value can be associated with specified nodes of interest.
Such data structures can be used in information retrieval applications, for example, to search files and provide results in response to search queries. A trie search can be performed relatively quickly for looking at input character by character. Tries also can be useful for implementing approximate matching algorithms. Furthermore, tries can provide advantages over binary search trees and hash tables for some applications.